package class_0927Treap;

import java.lang.Comparable;
import java.util.Random;
import java.util.Comparator;

public class Treap<K,V> {
    //比较器， 可以手动传递比较器对象， 否则K必须实现Comparable接口
    private Comparator<? super K> comparator;
    //随机数生成器， 为每一个节点生成一个随机数
    private final Random random = new Random();
    private Node<K,V> root;  //根节点
    public class Node<K,V>{
        K key;  //键
        V value;  //值
        Node<K,V> left; //左子树
        Node<K,V> right;  //右子树
        Node<K,V> parent; //父指针
        int priority;  //优先级
        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            left = right = null;
            priority = random.nextInt();//为新生成的节点分配一个随机数。
        }
    }
    public Treap(){
        this(null);
    }
    public Treap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }
    public Node<K,V> search(K key){
        if(root == null){
            return null;
        }
        Node<K,V> current = root;//遍历Treap
        int cmp = 0;
        if(comparator != null){
            //比较器不为空，那么优先使用比较器。
            cmp = comparator.compare(current.key, key);
            while(current!=null){
                if(cmp==0){
                    return current;//找到了！直接返回节点的引用。
                }
                else if(cmp<0){
                    current = current.right;//前往右子树
                }
                else{
                    //cmp>0
                    current = current.left;
                }
                cmp = comparator.compare(key,current.key);
            }
        }
        else{
            //comparator == null
            @SuppressWarnings("unchecked!")
            Comparable<? super K> comparable = (Comparable<? super K>)current.key;
            // 使用者必须确保K类型是可比较的， 否则报错。
            cmp = comparable.compareTo(key);
            while(current != null){
                comparable = (Comparable<? super K>)current.key;
                cmp = comparable.compareTo(key);
                if(cmp==0){
                    return current;
                }
                else if(cmp<0){
                    current = current.right;
                }
                else{
                    current = current.left;
                }
            }
        }
        return null;//出循环了即为空。
    }

    public boolean contains(K key){
        return search(key) != null;
    }

    public V get(K key){
        return search(key) != null ? search(key).value : null;
    }

    public void put(K key, V value){
        if(key != null) {
            insert(new Node(key, value));
        }
    }
    public void insert(K key, V value){
        if(key != null) {
            insert(new Node(key, value));
        }
    }
    public void insert(Node<K,V> node) {
        if (root == null) {
            root = node;
            return;
        }

        Node<K,V> current = root; // 当前节点
        Node<K,V> parent = null; // 父节点
        int cmp = 0;

        // 遍历查找插入位置
        while (current != null) {
            parent = current;
            if (comparator != null) {
                cmp = comparator.compare(node.key, current.key);
            } else {
                @SuppressWarnings("unchecked")
                Comparable<? super K> comparable = (Comparable<? super K>) current.key;
                cmp = comparable.compareTo(node.key);
            }

            if (cmp == 0) {
                current.value = node.value; // 更新值
                return;
            } else if (cmp < 0) {
                current = current.right; // 前往右子树
            } else {
                current = current.left; // 前往左子树
            }
        }

        // 插入节点
        node.parent = parent;
        if (cmp < 0) {
            parent.right = node; // 插入到右子树
        } else {
            parent.left = node; // 插入到左子树
        }

        siftUp(node); // 上浮操作
    }


    private void siftUp(Node<K, V> node){
        //上浮的临界是根节点，到根节点就必须终止了。
        //这里直接node.parent， 不需要申请新变量。---对可读性没多大英影响
        while(node != root && node.priority < node.parent.priority){
            //开始上浮
            if(node.parent.left == node){
                //执行右旋
                rightRotate(node.parent);
            }
            else{
                //parent.right == node
                //执行左旋
                leftRotate(node.parent);
            }
            //经过旋转后，原先的父亲节点指针parent成为node的孩子节点
            node.parent = node.parent;
        }
    }

    private void leftRotate(Node<K,V> x){
        Node<K,V> y = x.right;
        x.right = y.left;
        if(y.left != null){
            y.left.parent = x;
        }
        y.parent = x.parent;
        if(x.parent == null){
            root = y;
        } else if (x.parent.left == x) {
            x.parent.left = y;
        }
        else{
            //x.parent.right = x
            x.parent.right = y;
        }
        y.left = x;
        x.parent = y;
    }

    private void rightRotate(Node<K,V> y){
        Node<K,V> x = y.left;
        y.left = x.right;
        if(x.right != null){
            x.right.parent = y;
        }
        x.parent = y.parent;
        if(y.parent == null){
            root = x;
        }
        else if(y.parent.left == y){
            y.parent.left = x;
        }
        else{
            //y.parent.right == x
            y.parent.right = x;
        }
        x.right = y;
        y.parent = x;
    }

    public void remove(K key){
        Node<K,V> node = search(key);
        if(node != null){
            delete(node);
        }
    }
    public Node<K,V> delete(K key){
        Node<K,V> node = search(key);
        if(node != null){
            delete(node);
        }
        return node;// 不存在，则返回null,因为此时node==null
    }
    private void transplant(Node<K,V> u, Node<K,V> v){
        if(u.parent == null){
            root = v;
        }
        else if(u.parent.left == u){
            u.parent.left = v;
        }
        else{
            u.parent.right = v;
        }
        if(v!=null){
            v.parent = u.parent;
        }
    }
    public Node<K,V> minimum(Node<K,V> node){
        if(node == null){
            return null;
        }
        while(node.left != null){
            node = node.left;
        }
        return node;
    }
    public void delete(Node<K,V> node){
        if (node.left == null) {
            transplant(node,node.right);
        }
        else if(node.right == null) {
            transplant(node,node.left);
        }
        else{
            Node<K,V> leftMin = minimum(node.right);
            if (leftMin.parent != node) {
                transplant(leftMin, leftMin.right);
                leftMin.right = node.right;
                node.right.parent = leftMin;
            }
            transplant(node,leftMin);
            leftMin.left = node.left;
            node.left.parent = leftMin;
        }
        siftDown(node);
    }
    private void siftDown(Node<K,V> node) {
        Node<K,V> child = node.left;
        boolean isLeft = true;//左孩子还是右孩子，

        while (child != null) {
            // 选择优先级较高的孩子节点
            if (node.right != null && node.right.priority > child.priority) {
                child = node.right;
                isLeft = false;
            }

            // 执行旋转
            if (child.priority > node.priority) {
                if (isLeft) {
                    rightRotate(node);
                } else {
                    leftRotate(node);
                }
                node = child; // 更新当前节点为孩子节点
                child = (isLeft) ? node.left : node.right; // 继续下沉
                isLeft = true; // 重置为左子树
            } else {
                break; // 如果当前节点的优先级已大于所有孩子，结束
            }
        }
    }

    public static void main(String[] args) {
        // 创建一个 Treap 实例
        Treap<Integer, String> treap = new Treap<>();

        // 插入节点
        treap.put(50, "Value 50");
        treap.put(30, "Value 30");
        treap.put(70, "Value 70");
        treap.put(20, "Value 20");
        treap.put(40, "Value 40");
        treap.put(60, "Value 60");
        treap.put(80, "Value 80");

        // 查找节点
        System.out.println("查找 30: " + treap.get(30)); // 输出: Value 30
        System.out.println("查找 100: " + treap.get(100)); // 输出: null

        // 删除节点
        treap.remove(30);
        System.out.println("删除 30后查找 30: " + treap.get(30)); // 输出: null

        // 再次插入并查找
        treap.put(30, "New Value 30");
        System.out.println("查找 30: " + treap.get(30)); // 输出: New Value 30

    }

}
